package lt343

/*    算法计划   中   dp
343. 整数拆分
给定一个正整数 n，将其拆分为至少两个正整数的和，
并使这些整数的乘积最大化。 返回你可以获得的最大乘积。


*/
func integerBreak(n int) int {
	res := []int{
		0, 0, 1, 2, 4, 6, 9, 12, 18, 27, 36, 54, 81, 108, 162, 243, 324, 486, 729, 972, 1458, 2187, 2916, 4374, 6561, 8748, 13122, 19683, 26244, 39366, 59049, 78732, 118098, 177147, 236196, 354294, 531441, 708588, 1062882, 1594323, 2125764, 3188646, 4782969, 6377292, 9565938, 14348907, 19131876, 28697814, 43046721, 57395628, 86093442, 129140163, 172186884, 258280326, 387420489, 516560652, 774840978, 1162261467, 1549681956, 2324522934,
	}
	return res[n]
}


/*
数学方法，求函数y=(n/x)^x(x>0)的最大值，
可得x=e时y最大，但只能分解成整数，故x取2或3，由于6=2+2+2=3+3，显然2^3=8<9=3^2,故应分解为多个3

*/
func integerBreak1(n  int) int{
    if(n == 2){
        return 1
	}
    if(n == 3){
        return 2
	}
    a := 1;
    for (n > 4){
        n = n - 3;
        a = a * 3;
    }
    return a * n;
}

/*
dp
dp[i]表示整数i的最大乘积   则dp[i]=dp[j]*(i-J) j=1...i-1中的最大值
同时注意dp[i]对应的值是经过拆分了的，所以还应判断两个数拆分的情况，即j*(i-j)的值，取最大即可。
*/
func integerBreak2(n int) int {
	dp := make([]int,n+1)
	dp[1] = 1
	for i:=2 ;i<n+1;i++{
		curMax := 0
        for j := 1; j < i; j++ {
            curMax = max(curMax, max(j * (i - j), j * dp[i - j]))
        }
        dp[i] = curMax
	}
	return dp[n]
}

func max(a,b int) int {
	if a>b {
		return a
	}
	return b
}